package gold.gold05;

/**
 *
 */
public class S1721直方图的水量 {
    /**
     * 100, 比较简单。
     * 找到最大值, 然后从两边逼近这个最大值找出每个位置可以有的水量。
     */
    public int trap(int[] height) {
        if(height == null || height.length <= 2) return 0;
        int maxPosi = 0; // 记一下最大值的位置就行。
        for(int i = 0; i < height.length; i++){
            if(height[i] > height[maxPosi])
                maxPosi = i;
        }
        // 从两边逼近最大值
        int waterCount = 0;
        int tempMax = height[0];
        for(int i = 0; i < maxPosi; i++){
            if(height[i] > tempMax){
                tempMax = height[i];
            }else{
                waterCount += tempMax - height[i];
            }
        }
        tempMax = height[height.length - 1];
        for(int i = height.length - 1; i > maxPosi; i--){
            if(height[i] > tempMax){
                tempMax = height[i];
            }else{
                waterCount += tempMax - height[i];
            }
        }
        return waterCount;
    }
}
